"""
构建['i', 'like', 'apple']的trie树
"""


class TrieTree:
    def __init__(self):
        self.node = dict()  # 节点
        self.is_leaf = False  # 该节点是否是叶子节点

    def insert_node(self, word):
        """
        将单个词加入trie树
        :param word:
        :return:
        """
        # 创建指向头节点的指针
        curr_point = self

        # 遍历word中的字符
        for w in word:
            # 判断指针所指向的节点的子节点中是否有遍历到的字符
            if w not in curr_point.node:
                # 如果没有就将该字符字符添加为当前节点的子节点
                curr_point.node[w] = TrieTree()
            # 将指针指向当前子节点
            curr_point = curr_point.node[w]

        # 遍历完成设置当前节点是叶子节点
        curr_point.is_leaf = True

    def insert_many_node(self, words):
        """
        再字典树中插入多个单词
        :param words:
        :return:
        """
        for word in words:
            self.insert_node(word)

    def search(self, word):
        """
        查询字典树
        :param word:
        :return:
        """
        # 创建指向头节点的指针
        curr_point = self

        # 遍历word中的字符
        for w in word:
            # 判断指针所指向的节点的子节点中是否有遍历到的字符
            if w not in curr_point.node:
                # 如果没有直接返回False
                return False
            # 如果有,就将指针指向此子节点，然后继续
            curr_point = curr_point.node[w]
    
        # 能够再字典树中查询到此单词，返回成功
        return curr_point.is_leaf


if __name__ == '__main__':
    build_words = ['i', 'like', 'apple']

    trie_tree = TrieTree()
    trie_tree.insert_many_node(build_words)

    print(trie_tree.search('apple'))
    print(trie_tree.search('I'))




